Comptage de chaînes

 Propriété Nombre de chaînes de longueur  $k$ qui relient le sommet  $i$ au sommet $j$

Soit  $n$ et  $k$ deux entiers naturels non nuls et  $A$ la matrice d’adjacence d’un graphe  $G$ d’ordre  $n$ dont les sommets sont numérotés de  $1$ à $n$ , puis rangés dans l’ordre croissant de leurs numéros. Le coefficient de la  $i$ -ème ligne et de la  $j$ -ème colonne de la matrice  $A^k$ donne le nombre de chaînes (ou de chemins) de longueur  $k$ reliant le sommet  $i$ au sommet $j$ .

Exemple

$\begin{array}{cc}A=& A^5=\\ \\ \left(\begin{array}{ccccccccc}0& 1& 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 0& 1& 0\end{array}\right)& \left(\begin{array}{ccccccccc}2& 22& 6& 9& 10& 3& 7& 8& 8\\ 22& 24& 3& \mathbf{32}& 46& 36& 10& 18& 11\\ 6& 3& 0& 8& 9& 13& 2& 6& 1\\ 9& \mathbf{32}& 8& 18& 31& 12& 9& 11& 15\\ 10& 46& 9& 31& 24& 19& 21& 28& 12\\ 3& 36& 13& 12& 19& 4& 9& 10& 19\\ 7& 10& 2& 9& 21& 9& 2& 3& 7\\ 8& 18& 6& 11& 28& 10& 3& 4& 14\\ 8& 11& 1& 15& 12& 19& 7& 14& 2\end{array}\right)\\ \\ & \text{32 chaînes de 5 arêtes}\\ & \text{relient les sommets 2 et 4.}\end{array}$

La démonstration se fait par récurrence sur $k$ , à  $n$ fixé.